package datastruct;

public class RedBlackTree {

    private final static boolean RED = true;
    private final static boolean BLACK = false;

    private Node node;

    public RedBlackTree() {
    }

    public RedBlackTree(Node node) {
        this.node = node;
    }

    public Node getNode() {
        return node;
    }

    public void setNode(Node node) {
        this.node = node;
    }

    //判断是否是红色节点
    private boolean isRed(Node node){
        return node==null?false:node.isColor();
    }

    //查找指定的值
    public String getValue(Node node, String key){
        if (node == null){
            return null;
        }
        int cmp = key.compareTo(node.getKey());
        if (cmp == 0){
            return node.getValue();
        } else if (cmp > 0){
            return getValue(node.getRight(), key);
        } else {
            return getValue(node.getLeft(), key);
        }
    }
    //左旋转
    public Node rotateLeft(Node h){
        Node x = h.getRight();
        h.setRight(x.getLeft());
        x.setLeft(h);
        x.setColor(h.isColor());
        h.setColor(RED);
        return x;
    }
    //右旋转
    public Node rotateRight(Node h){
        Node x = h.getLeft();
        h.setLeft(x.getRight());
        x.setRight(h);

        x.setColor(h.isColor());
        h.setColor(RED);
        return x;
    }

    public Node flipColor(Node h){
        h.getLeft().setColor(BLACK);
        h.getRight().setColor(BLACK);
        h.setColor(RED);
        return h;
    }

    public void put(String key, String value){

    }
    private Node put(Node h, String key, String value){
        //第一次添加元素
        if (h == null){
            return new Node(key, value, 1, RED);
        }
        int cmp = key.compareTo(h.getKey());
        if (cmp < 0){
            h.setLeft(put(h.getLeft(), key, value));
        } else if (cmp > 0){
            h.setRight(put(h.getRight(), key, value));
        } else {
            h.setValue(value);
        }
        //平衡化操作
        if (isRed(h.getRight()) && !isRed(h.getLeft())){
            h = rotateLeft(h);
        }
        if (isRed(h.getLeft()) && isRed(h.getLeft().getLeft())){
            h = rotateRight(h);
        }
        if (isRed(h.getLeft()) && isRed(h.getRight())){
            h = flipColor(h);
        }
        h.setNumber(size(h.getLeft()) + size(h.getRight()) + 1);
        return h;
    }

    private int size(Node node){
        if (node == null)
            return 0;
        return node.getNumber();
    }
}
